package leetcode_周赛._2022._202207;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/7/3 11:12
 * 300 场周赛
 */
public class _03 {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1, new ListNode(2));
        new _03().spiralMatrix(1, 4, head);
        System.out.println(new _03().peopleAwareOfSecret_prefix(684, 18, 496));
    }

    /**
     * 6111. 螺旋矩阵 IV
     * 算法：模拟
     */
    ListNode head;
    public int[][] spiralMatrix(int m, int n, ListNode _head) {
        int[][] ans = new int[m][n];
        head = _head;
        if (head == null) return ans;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) ans[top][i] = getVal();
            for (int i = top + 1; i <= bottom; i++) ans[i][right] = getVal();
            if (left < right && top < bottom) {
                for (int i = right - 1; i >= left; i--) ans[bottom][i] = getVal();
                for (int i = bottom - 1; i >= top + 1; i--) ans[i][left] = getVal();
            }
            ++left;
            ++top;
            --right;
            --bottom;
        }
        return ans;
    }
    private int getVal() {
        if (head == null) return -1;
        int val = head.val;
        head = head.next;
        return val;
    }

    /**
     * 6109. 知道秘密的人数
     * 算法：前缀和 + 动态规划
     * 没做出来，在做的时候想到了 dp，dp[i] 表示第 i 天知道秘密的人数
     * 但这样很麻烦，包括了刚刚知道秘密和之前就知道秘密的人数
     * 看了题解，将 dp[i] 表示成第 i 天新增的知道秘密的人数，这样 [n - forget + 1, n] 是知道秘密的人数
     * 哎，不会转化思路
     * 为了方便，使用前缀和
     * 定义 sum[], sum[i] 表示前 i 天知道秘密的人数
     */
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int mod = (int) (1e9 + 7);
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int l = Math.max(0, i - forget + 1), r = Math.max(0, i - delay);
            for (; l <= r; l++) dp[i] += dp[l];
            dp[i] %= mod;
        }
        int ans = 0;
        for (int i = n - forget + 1; i <= n; i++) {
            ans += dp[i];
            ans %= mod;
        }
        return ans;
    }

    public int peopleAwareOfSecret_prefix(int n, int delay, int forget) {
        int mod = (int) (1e9 + 7);
        long[] sum = new long[n + 1];
        sum[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 这里相减可能会出现负数, 比如一个数小于 mod, 取模后不变. 另一个数大于 mod, 取模后变小了
            // 在相减的时候要在加上一个 mod, 防止负数
            long f = (sum[Math.max(0, i - delay)] - sum[Math.max(0, i - forget)] + mod) % mod;
            sum[i] = (sum[i - 1] + f) % mod;
        }
        // +mod 防止负数
        return (int) ((sum[n] - sum[Math.max(0, n - forget)] + mod) % mod);
    }

}
